/*
 * @lc app=leetcode.cn id=887 lang=java
 *
 * [887] 鸡蛋掉落
 */

// @lc code=start
class Solution {
    public int superEggDrop(int k, int n) {
        int[][] dp = new int[k + 1][n + 1];
        int m = 0;
        while (dp[k][m] < n) {
            m++;
            for (int K = 1; K <= k; K++) {
                dp[K][m] = dp[K][m - 1] + dp[K - 1][m - 1] + 1;
            }
        }
        return m;
    }
}
// @lc code=end
